package T21_30;

public class T26 {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public ListNode detectCycle(ListNode head) {
    /*思路：假设从头结点到环的距离为a，环的长度为b，环的入口结点到快慢结点相遇的距离为c（此距离为最短距离）
    * 当两节点相遇时，fast必定领先slow一圈，fast走的距离f=a+(b-c)+c=2s=2(a+(b-c))
    * 可以得到a=c,即头结点到环的入口距离和fast和slow第一次相遇时结点位置到环入口位置距离相等
    * 此时将fast指向头结点开始移动，速度和slow一样，当再次相遇时，会在环的入口出相遇，返回目标节点*/
        ListNode fast=head;
        ListNode slow=head;
        //找到第一次相遇的位置
        while(true){
            if (fast==null||fast.next==null)return null;
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow)break;
        }
        fast=head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }return fast;
    }
}
